#include <vector>
#include <algorithm>
#include <iostream>

using std::cout;
using std::vector;
using std::sort;
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> vv;
        sort(nums.begin(),nums.end());
        int a,b,c,d,left,right;
        long sum;
        for(size_t i = 0;i < nums.size();++ i)
        {
            // 减枝
            if(nums[i] > target && target > 0) break;
            a = nums[i];
            // 过滤a
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for(size_t j = i + 1;j < nums.size();++ j)
            {
                if(a + nums[j] > target && target > 0) break;
                // 过滤b
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                b = nums[j];
                left = j + 1;
                right = nums.size() - 1;
                while(left < right)
                {
                    c = nums[left];
                    d = nums[right];
                    sum = (long)a + b + c + d;
                    if(sum < target) ++ left;
                    else if(sum > target) -- right;
                    else
                    {
                        vv.push_back({a,b,c,d});
                        // 去重
                        while(left < right && nums[left] == nums[left + 1]) ++ left;
                        while(left < right && nums[right] == nums[right - 1]) --right;

                        ++ left;
                        -- right;
                    }
                }
                
            }

        }
        return vv;
    }
};


int main(int argc, char const *argv[])
{
    Solution s;
    vector<int> v({2,2,2,2,2});
    vector<vector<int>> vv = s.fourSum(v,8);
    for(auto &v : vv)
    {
        for(auto & num : v)
        {
            cout << num << " ";
        }
        cout << "\n";
    }
    getchar();
    return 0;
}
